package com.leecode.acs;

/**
 * @description: 美团：
 * 来自美团 8.20笔试
 * 小团手上的两个数列分别为A和B，长度分别为n和m。小团很想再次让这两个数列变得一样。
 * 他现在能做两种操作:操作一是将一个选定数列中的某一个数a改成数b，
 * 这会花费Ib-al的时间操作二是选择一个数列中某个数a，将它从数列中丢掉，花费lal的时间。
 * 小团想知道，他最少能以多少时间将这两个数列变得再次相同!对于所有数据，1 < n,m < 2000，
 * lAil,IBil  10000输出一行一个整数，表示最少花费时间，来使得两个数列相同
 * <p>
 * （解法一）暴力递归解法测试
 * @date: 2023/1/9 22:00
 * @author: yaoshubin
 * @version: 1.0
 */
public class ACS_01_数列最小代价 {

    public static void main(String[] args) {

        int[] A = {1, 2, 5, 7, 9, 1, 0};
        int[] B = {1, 3, 5, 7, 5, 1, 10, 3};

        int min = zuo(A, B, 0, 0);

        System.out.println(min);

    }


    //zuo(A,B,0,0)
    public static int zuo(int[] A, int B[], int ai, int bi) {
        //A[], B[] , A[1,2,3],B[1,2,3]
        if (ai == A.length && bi == B.length) {
            return 0;
        }

        //A[1,2] ,B[1,2,3]
        if (ai == A.length && bi != B.length) {
            return Math.abs(B[bi]) + zuo(A, B, ai, bi + 1);
        }

        //A[1,2,3] ,B[1,2]
        if (ai != A.length && bi == B.length) {
            return Math.abs(A[ai]) + zuo(A, B, ai + 1, bi);
        }

        //A[1,3,5] ,B[1,4,7]
        if (ai != A.length && bi != B.length) {
            return Math.abs(A[ai] - B[bi]) + zuo(A, B, ai + 1, bi + 1);
        }

        //可能性1  A[ai] 删掉
        int p1 = Math.abs(A[ai]) + zuo(A, B, ai + 1, bi);

        //可能性2  B[bi] 删掉
        int p2 = Math.abs(B[bi]) + zuo(A, B, ai, bi + 1);

        //可能性3： A[ai]->B[bi] , B[bi]->A[ai]
        int p3 = Math.abs(A[ai] - B[bi]) + zuo(A, B, ai + 1, bi + 1);

        return Math.min(Math.min(p1, p2), p3);
    }


}
